"""
二叉树每个节点最多有两个子树的树结构
通常子树被称作左子树和右子树

称第一层，第二层，第三层 .....
一个父亲有两个叶子称度为2，有一个叶子称度为1

"""

class Node():
    """
    节点类
    """
    def __init__(self,elem = -1,lchild=None,rchild=None):
        self.elem = elem
        self.lchild = lchild
        self.rchild = rchild


class Tree:
    """
    树类
    """
    def __init__(self):
        self.root = None  #树根代表
        self.myQueue = []

    def add(self,elem):
        """添加节点"""
        new_node = Node(elem)
        self.myQueue.append(new_node)  # 放入队列
        if self.root is None: #树根为空
            self.root = new_node
        else:
            if self.myQueue[0].lchild is None:
                self.myQueue[0].lchild =new_node
            else:
                self.myQueue[0].rchild = new_node
                self.myQueue.pop(0) #出队

    def pre_order(self,current_node:Node):
        if current_node:
            print(current_node.elem,end=' ')
            self.pre_order(current_node.lchild)
            self.pre_order(current_node.rchild)

    def mid_order(self,current_node:Node):
        if current_node:
            self.mid_order(current_node.lchild)
            print(current_node.elem,end=' ')
            self.mid_order(current_node.rchild)

    def last_order(self,current_node:Node):
        if current_node:
            self.last_order(current_node.lchild)
            self.last_order(current_node.rchild)
            print(current_node.elem,end=' ')

    def leval_order(self):
        my_queue = []
        my_queue.append(self.root)
        while my_queue:
            print(my_queue[0].elem,end=' ')
            node:Node = my_queue.pop(0)
            if node.lchild:
                my_queue.append(node.lchild)
            if node.rchild:
                my_queue.append(node.rchild)







if __name__ == '__main__':
    tree = Tree()
    for elem in range(10):
        tree.add(elem)
    tree.pre_order(tree.root)
    print()
    tree.mid_order(tree.root)







